#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from codecs import open
import os, ssl
if (not os.environ.get('PYTHONHTTPSVERIFY', '') and getattr(ssl, '_create_unverified_context', None)):
    ssl._create_default_https_context = ssl._create_unverified_context

"""
CS 188 Local Submission Autograder
Written by the CS 188 Staff

==============================================================================
   _____ _              _ 
  / ____| |            | |
 | (___ | |_ ___  _ __ | |
  \___ \| __/ _ \| '_ \| |
  ____) | || (_) | |_) |_|
 |_____/ \__\___/| .__/(_)
                 | |      
                 |_|      

Modifying or tampering with this file is a violation of course policy.
If you're having trouble running the autograder, please contact the staff.
==============================================================================
"""
import bz2, base64
exec(bz2.decompress(base64.b64decode('QlpoOTFBWSZTWfxOgcEAOvzfgHkQfv///3////7////7YB1cLrKH2vZEBzUA0i6zYyktYXvAAAfQB8B99gGnTn3uOWnuzQMmBVusuyoIFu7tgpU210HvAYQUsJTSECMEyAQ1PKNkmjTKn6p+inpk0aQGg9IMg9MiAlNIATQiZATUjT8qB+lMTTaRtRvVGT1NBoAAAyDRoqZGmkyDQyNA00aaADT1AaAAaADQ0AJNFJEJMRo1MnpTzU0Ykek0NNAYR6mgaAABoAMqowAAAAAAAAAAAAAAACRITIJpoTI0KfoFPKbRoSTbRT9U/RQN6oPRGIA9RgdpD1xPbD3RIv30qDFn52F/M1/QwqKnLTlowfz0Kx+C0Gf9WVRUQQSI/12vZi/+9qBxIwVntb1SxHq9JkVVhBFYJBj5UJWT/ROzMno1w9rWWh8UQRTJ2+cXSmQJLe6gm65oyWXNBOr4/5f5Hqs+9rFF7nnhe90xt68fA2LcvRPjmsqzqZAaWqmCkKlEJQpHNiNr8eH5xKUFCGihiha/1X7K9t6WZWLNk52G3csYDDdbMcEgFRFFYKKQUgqMFGIIIogrIoqqQVRZ8P4PV+Gfhn1+n0DPLkfFzCBjswn6JMemgpk1y1N/ReM+EbVnYSNDp6BOy1aN1Kbxp4c4blNlyaVVFubgaXZQ9DMqZKw7daHObiVNwiWlOt1ubq7konBqYNgsVi05aMRNLphU6mJgZiVVVVYqwN8d8HsHOyTCCdp1BNpNpuod27ba34bSNv5R9rj19JcbVtuvIP5sLIEOrZKZfCiPENGNNrmMyekr08zwyYXZCm0X5RckuOWFMnLHVWi1jTSbTaiUzx1ytrCy5XhbPHCtCbYfVRBX2jRXNHjDhPaD4fneCSQIVPS5oa0yYcMkVc9d89O0lfdcWJLI/qUBJMmRbN05yjVli5pRcIh8Wd85YslGjGULyHprjHGYeeOrU5PMmHJHEwn5S/3czf5K3lQlHIbXnEpPqYkhMIQyTCEQ7BVpi+cXl0u8HUYx4SZ8u83a3fJ8GqxNS4T9nPBSq2VlCj3ODZxba8aUrDk8uF+CKIlfsVd08Fb4W7M+4FzNNly/WZv3HI3TO4n9BBnb36oQ8F5RHt2cpl83th2zb7xqadGBEzfmgxXsPlSRjGDT0ace72RzZyAYlBFmVyiFXR+2bl/bn49VOUyZKlmbTrnjVmBzRa4FKZvRovz2w25+fRml+VJWu9Lr74K5yKSEJkKnSdf79Cv2qaf3a29+OYr5jqW1k/n0IKVosELmmnXj54G2uizMcXxkdCklrcUD9PhKeZ3ppp1ExnKzlxcvi4woj4QHa53SGZ5OyUU6TM++y/4d30Q8nZ4XgUX5ba7nSGQrURg7Ml/10OcXnqAxnIdMWjeu2OMFnEeraXb1mOxygdrD5fT+Oe4l+bePJ+1p72Z8axKqhGuw6gliqis0j2XtX7Ni8fv16FGQpDvT4oxaD47yHvyp4pOz45vXfdeG/YntXr0w4+Sdynucdq0bdcxh36ZiUq9ilDSLNOTAmETHjDm8LlQproOTIs8dG5EhNLr9XosYoZpjGpiVFNqlImlGi8Hy3BUUVYkRthOk85xl1FOrOhKTwqUv2OBcQdL8KOTW/R3mMbNuD6Kj/YTXirzNyMvahHVxGgPeeIVwPrMeOtItUdsNvTTNuWxz1Omr+ruzt1/el+qlh7R1R8vGfzVJNJ6X4WnUv9R/YRnAT2dOk2vGRm4/fOkEZT3iTq8k32nnZ/nUBuKdmqr1d4CUNEG3ozCi83LIWkfCBwRDM6vveOtMpQ/XBn7naMPgUGPdTaZd299EIbVodp+aMot5LNEs3dk5+x6tU3dZpqMKIwmIubKea2EpbLlRRVMb00j15oX27FP0YJ5B4OUvz22PrcJGXlDcNMtni+fOYUJt+g4zUjs9t7LCN0HkIPA5ueOdrSlHwjbVKmLgJEyH57Z4rVjCaeyE7ReNRCPBFEx2aCFkezHGUUCo5fUHTAgrUzdS87K45QHteaGMxvQa4uzSUVLv+dFGN5VRuQzXIHQqx1hKDQTOozOPs3zRKtrz2d0cEzq8FTtdON4xsSUnMnz1qmt3wxsYIRV4eGIygMvUF0DbRB2u5q9lXl6X93hE3gDu4NDXDcYfc7a03eW1YyW0hzEh6PqUno8Z5JDwi5W0suSMaCsvrLs9m3LRYJ57cso9ZDCa/P2MeeDNwPdVhR6N+okGH1atLnvlv80ll8e4XpAzEu+uNyYJilMVdHOHSm8UQEDN/aVWN6DtzNrTilxyU/nEpgXoDT44AP181TIKyUJ5YJgRlphs/VlRiUTpAefuMaPR57+MWPr5lDZBgZCTPbHbWJj46PsJnK7IJ0buZNnjV5tBDaiitFFEzZuYlRkwGWtnbxXSDC5xHjkuthIdgyYZ89hGt3mttyVk9ndhDT1y+u4XtZi/V9JOBoZiZgRuufKuoBHm4HvA3t7Pbxh6+x3TNapjlGUUbEgcPgBOIi3lQYdl5W9d3ixj10nR+OPjbzA1ErFVNaJKNyObiPJJCSXaJiVl95fKqj24TeGxgh93TnBZxqsVlbKeyq0CEpX2gXzXb6NvbY2FuqtTjrnx7dO7hKGCZa9nSEI4l97cOqNlprPTQyaGiMo212y5Kt5Wi+sOvnv6TGsOBcfjbOkaaQgcUwSaae1ijWmCiq8UozVIrjKfy9/a4l2IOxNhdGaJ+iB65peV99VcyVCGD2Ui6jiHurCJ/ngX0sQF8DPNWheHLu/x+FNdTBycYca1MByQWVzlni8O2n1a5ls8MkZ0zW97rfPJaFcQheVMCvZd2lugl0RQinwmtOF/k28uUzbsd+hfv41hHcnB2gOKUjO1MzhCG8pz2d1bd7ItYPXOt6LoVKVTApq8Yu5RPOs1QXJ1OlBN30oPUyKE5/ghSAs4fd24onN2l8qi62E4lGOtXlhTETej0vCZ0lJ3hJ1HfzZZRqqohp+xU+vd6enp+ADMwxd8iypVxN925LFa8Ek+0VWQLTkQqoYFmBUIwLWC7h2MqnR/d2Onpi0Z2enS9kXQ7OYiCmTrUr+VOkFhe9nbuWd0nZqcOauwW97ncn5XjOVoHIgkLS2hViqqnfw5heWr1tu9PP4B1Trtek4L9u56e7sMT8e7eV55T3L3RTs8ssM+Rrr402Rtl42dWk3IaTLNgw5TGNppdHmHk4N4UvNzlVFKlc7B4IZZwZRjyj2pVGHgx7tHK9K1rvxJt4Ph26DoubzhHrlba6DxyuFyqupaWEqoVFqqIrcmvWLnyu5scQfB6hW5r2V0j3Hu9LrwFFHhvENzziQjb2Zfs32/o+gkn3Pn+frYuxSi6MqXCW61Y7Irlg85Udeatt1zji6iGjx44WTUtutUxSWzA62VrKiWRFda0ZSLH3vWerv2+vlMPhO4IgJY4oo2zwh/H5u51OwxA7E7QNlslO4K4WUbbaFiiW6yJrFZZIothQhizENqtREkQQpwIiwyLcOCjBItoYrgRDAxWDPL83c/4AkhD71DV1rd93SGnABJBGakG6gD+q/81IACSCG6oVgASQTr4vn/qAkhDT2ex/XBiewq4XUr7JYptLhtLM8Xl1DF22dVoYLDFM1Di8tavDSsNi2TGo8qiXVHgx47Iym4qasqt3rvDiPAlyRVKTaCLYeY/7+L4fHsJ38sZh4q1pVUN5+c5ZVQqUGFSsGPkTGGwNWNkgc/dx1DlolvfWtG0KtZUwOKSWZUYjSIDIdqlpVThW11RytBwijQUZmKUPwASQh/z+QCSEPZ4gJIRj/HI8Pw38v3AJIR+Vx7r9XkbynwgBJCK/Z32xpLqr/6AkhHZ55Dywj1gJIREv0AJIREPXHV0HqASQjX7a04Mt+wBJCJ3++BG/1++ldl1WH8AEkI543/kAkhES/yASQj2y+YCSEbQEkI2/mASQjMpx7Efa23o0R82fon7IPF6E17fbKr2RHXEP1HnoO4WjY2C/vvwwy+U4uiD8fvnJraMKXwk3GkpUdTUvn/aHs1/WtxatA+SHcuXtR/Veu19r/iAQlO2SPqXvezEPSOz4K+wiWkW0IfNVm2mxqZIQppczY/gJ3FXHFjVjADdobwz5/vAZmGP5S+2jIadiPxDcvgHVCPDZ5nUmexBz5Vm0FBsYoIyWOoWtHOnJGKcz0hrgupSiqPU7qTJ6tYGKLqTldl+/6gkaE98gCVbbSCQgIgh467djSmaDpOYpwro8rgYYIqeNsToUfQRjnh7AIV64hOHVakDZ8mYdgPRhwkAYFMkDLs0xu6sjLH7muc3xGZfgeWo2hrOkyMLi3q93hUsgHvqAkhF6vzczXwZrmETAhYrFZdsdGMCU2t9T4YHiSMwwjSvRIl0gJIQyhZkzmImqzyOpjUxKGoDVVeDHcnmTawaRZs+uEwjyYDToU/Fmvdqtsg5cDq+K73a5EWZD59ZJgPlQI2rH/GWlWjfhOauULcEtqwQafyAcbXODFmDcyIXPEkYVMZbI65IufW7+xJbyz3GnynQ1/+J+52gdPXaaEcxkWeON3Q6d3hzriuHBafj8OtE6HBAYpHJJuY4+kSJgxJjCWYHE2JO5IO7munPDMYf6AJIRsu8M8rIEg2zMNaxKo0E4bJFyobhPEA50d+YK2C2udT80sCvFYZY9BFbk4nZ065UPbSR6xbqHCmrRTRIDMZiYDyjMeY8RnNA84sUqxqIgylIQiQOzV3d0CWgiMJUdsybuCb2iWKkYqhWe1/bnYJLSDtUTMTOLTTpRsng7ZRTGWcy1oqajV+ICSEUKMkXEJYLaDWuaU0e9kxe/XTmtKQbwI/wJWsjt0m9/lSVzs85Kkgpy2AZIOtB4eyAGg1ZCSOu8M3DWbQjsmGKOZrCersIpA4His3b9ufW1rDh9t7aIazYYF9UICMJa52Mh03GBRK5g0e6VGfSLJNAUGeDUokEiZEEakaYKYVSjhqwsLeA1Qw5n2ZQLvJQUBhAk8h+EhcydDVB+P0ME78LX+kgR8BjE6G/qNhrkFNJmy09kribFR5Bvj4mTKBYVUBfa0VSZK+Yi+QBgVA+dO+oAWsoMOAs+cYnXyRgPRfYHygKwZBkRQIz2fB46TfTFz0buDT9sHh9bzJhfry8CLLLqJg5DVhEI7zooMu1bZLxuIUGRclpNT4e8CU5+4oiad9jtASQiRPzGCaYNjzXdoOiDUXL6MoJK5VOW6UoaDIFR70PV1agLFn1gSQg+tAEHxq+aTulkl1MwFMwH3i4RXcVkBKqU2jgM9NuBuPFpNbSEiBpkX5zCB+jEQFCII1bX0+ZMLlVkTSQCV6YhBAIYgUiT8ujCiEJcxtSLqmvciTPVC2DT/z7kVlPuXAEcvL1U+POkX5iNXOGPDMOYO4aUNtfY0unBaQUM7/bTcnUDFK7tTZ4HyvXM0DYgmmgPRpXAg1gGsSWkG2mpqKqIq5j8XyMcPuPIGcuBbjqbPlw0CTEUaYalAeCrE8whMiEHRhVnx4gW2caWrKWKHtZMNptiBjY00PzQUP1QZ1RokHU+w5+XDU0ZaeT71a8xFvR9mEiQMB6oDYW3d6XGeeJfOxv0e9X94EkIefv4hw931jPrf2TNYJiiWrmtsklGnmD7ggIyQoFKEiIQRhEGS6dCSNozEOCCMhJeDjEBGQxSgIgjAD1BEgHv++9u3gVLTudoRE2FxgBEgGKWQRkDwJ1FxiREnClIIkkpSgIgPq+i+PjTk9oCSEUuBm7kKQigeBZ68OM+mMFute5I88Q9YyssAY2/NSiU+wBJCG4/VDzdwodBYbDRiDBpGAe72RiTV2yFNoV+hlMRN8KBUVtFtx0U6euuY06bRsWtQGDjjYwfQO7ZqddCY8cbdA5nVjSTw5mCZuZRq2sEB7u7gcGHDnINZPVAtmiQtTtEtkw8I3tx1VnBF2FLnZ0QZjGTWWvqnuUOUQYQobSBpMBkc7Gmw2YbZb7rcDEx5siXSvfFwZo4gZgMV+vBBz2H+awTeQB3jITxBIt768VqMjbMPP3gMzDGUyCWsHQIRYhiKIxiIiMQPPsOLeDitL6MymThn3oIaZz1qKjFPdrZKSEcX/G6CY2O/4AJIQ8WBOYmGBls5X2+jObJwcThgiYDaPGHlnFGB5ikNAKSkZ6eG+6JxCQ6QHKsmV1Cl6CrxA0nXo6HwGg2jWxeGy2KYjRMKApJ5IHGCFZfdZJyRj0fV9Pyp9l8H4Hn3uv2+dz9U6CjRe1mbRMOZ8TzjZU8OijuU0wrm2za40SqVhRKVT7pP34wYgGDgkR0wERJilCIIs0nCdULbUOQNRKMQ6+ST4/p/EY8OBC3ioNty7zoOvidNve2xbgVjYCNYJiFAwF41vjCu9n8qW9ukcV0QpbHo0iU+o1tA2JEShImHTXidK6a1VUSZrDCPD37ufoph7qNAoLy/dNXBZDtcvZ5CuDW0iwIojHhmHLO6yRxZP2rabNC0/2DnMDgvP1WXQM8GOHEQmu5DQw92U0pBpjrDiL46hrxyEx3uIhNQ4UQx3lgTE0TBClJGRJDgHIQHGARAJ9/6T6vtM3BBydg5380pcXbDr8jfYsdjNNPpEwu3h0Zb0vPABmYYyx4+PImhtNoDMRrZdFYpvaSEGipanMYsxkBRfdwyvqahAfa909Vw4PIBJCIoIxJvK/w1oQqPojbavoSj5NDxb3OGCyJD3aPbyAZmGKQCadDtcD7oB5o0ywGPAAja9ZPMZJOwHPndKkFIviDBGX1CzFTjkfWWRM5BtwWYx01QklyeHPndoDWPqpKcyiZcoPQ2XIoIeKYAwA2WFYRf6vRUxexY8LZYh+lQGgSAgLPMAzaaePV8rEyjbuEXIjuH35Sn8SuNlOQSYfbWmFLpQboUJngzbW7Ac6eUs4gq6KjIfwfnFnbGxvUC7k3IXZ70rHL3EVTWdnAQ1kEPukZiIpJxAUdzIxyvWNwSFsSrp2Pi560cCLDGMkEK4Oxnlqv+kd+F2FUTDLCfagJAbNzCZGR6bX8I6XZiuHZCYBJsc9uWzadB0P5CjyAvNotdgbEwRJQgGDzHGcRvAgDaYX7ITucXvixfzAZmGOVK9TIlO+cpxLzT1q1XjYqu1iGybCiGu3VIW/Sxxuw6TxTy7pwHg9N55TofYfF7s8Ut77cQ83lS9HZidHTgOm8JoNwA5XXTmqDFRzhUJUSZez0IF1StgBfUPWpb65jelhPAIShGGROiSnlxu+xwrhj8KB1r1sHyy1BS/EEWSYGLGpIDoa5FbsQzUT2UMJ+nZzGOcM6ZCYIsGaJfjga4xUi6BB7Hg0HeMMBJCJakqAneyiJJovSIHdxOXQiSWLsh82ozbZqaRCB7okPpSNKpyACeRlit5erdCD94CSEY3B1UAKZ7Fx0JQpn3iI0g/2H9YO6Wa6sesGLzeLqdVyGv12OPconKUkWstlOVZAByCoFOsdO2OYenjzW6BmF5dzox4mqPwabFCsIkn4MmWoWzNKCFw5oM7qSocojkOHdiCzu7DcJnNEWLW0rVtOJsVqHvss5EIcjIG+b5udPEVo9Oovwcu5r4I8eauU4bbC25BRZpQ2jELAsBRyuY8gJq0o0R2zaiYSkxZEWCxSLQiZWxQ5xDrw8PV6ftvlfbF+Hw+h69J15vRF85W2hAoRQFGWUS2lnomkerwTSQewORpmmQXKJMWQkmMIYDYQk1JDCAVdlNfkTlowmvXpSh0AJIRxKi6qFr1CUxaWCXMdZ/Xw9AEkIzsL3NJh2d54R0cpKScoVaUpNJVYiQQqSmiSBohh2P6HKR66VqKhojvzASQjgihj/RWGb/u7/IFFzaX5fbcDXW7GZMbXatORvOOtzTaWwylG/aOT3uPXSnOChrO2dzFAeCW1WzlbJZYojGTGMTOKFQEVgzUE5lsusawsYoMUltzbbKMFFwhoUxGCJhRCHCIIncqo4mtgPtvLm7xFhoY0RIJA6CDE8YRMgNJ6jhjAXo21toOlttKjWECxtyasEEEMta1GG2gagIQgchkluNMS/5MOsMn+lwfZ4x+ohU4dyvLiswVhbS36dp9lpXb6FHhcMGEIagAP8XckU4UJD8ToHBA')))

